package com.maltys.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/non-overlapping-intervals/">⽆重叠区间</a>
 */
public class NonOverlappingIntervals {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int cnt = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i - 1][1] > intervals[i][0]) {
                cnt++;
                intervals[i][1] = Math.min(intervals[i][0], intervals[i - 1][1]);
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        NonOverlappingIntervals intervals = new NonOverlappingIntervals();
        int overlapIntervals = intervals.eraseOverlapIntervals(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}});
        System.out.println(overlapIntervals);
    }
}
